package com.yoshino.leetcode.improve40.twentyeighth;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 回溯
        // 防止 1,7; 7,1
        Arrays.sort(candidates);
        // 从前往后遍历
        dfs(candidates, target, 0);
        return res;
    }

    private void dfs(int[] candidates, int target, int cur) {
        if (target == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = cur; i < candidates.length; i++) {
            if (candidates[i] > target) {
                return;
            }
            if (i > cur && candidates[i] == candidates[i - 1]) {
                // 防止重复
                continue;
            }
            tmp.add(candidates[i]);
            // 从后面接着遍历
            dfs(candidates, target - candidates[i], i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        // 回溯， 交换
        for (int num : nums) {
            tmp.add(num);
        }
        int n = nums.length;
        backtrack(n, 0);
        return res;
    }

    private void backtrack(int n, int first) {
        if (n == first) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = first; i < n; i++) {
            // 动态交换:从当前位置开始
            Collections.swap(tmp, first, i);
            // 递归下一个数
            backtrack(n, first + 1);
            Collections.swap(tmp, first, i);
        }
    }

    boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 回溯，判断: 不能用交换，重复判断条件不符
        visited = new boolean[nums.length];
        Arrays.sort(nums);
        backtrackUnique(nums, 0);
        return res;
    }

    private void backtrackUnique(int[] nums, int first) {
        if (nums.length == first) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 1,1,2，没访问过说明已经遍历完
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            tmp.add(nums[i]);
            visited[i] = true;
            backtrackUnique(nums, first + 1);
            visited[i] = false;
            tmp.remove(tmp.size() - 1);
        }
    }
}